/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._28;

/**
 *
 * 实现 strStr() 函数。
 *
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._28
 * @ClassName: ImplStrStr
 * @Author: linyaonan
 * @Date: 2019/10/12 15:35
 */
public class ImplStrStr {

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        if ("".equals(needle)) {
            return 0;
        }
        if (needle.length() > haystack.length()) {
            return -1;
        }
        if (needle.equals(haystack)) {
            return 0;
        }
        return getIndex(needle, haystack, 0);
    }

    private int getIndex(String needle, String haystack, Integer index) {
        // 取出第一个需要查询的字符
        char needFirst = needle.charAt(0);
        // 需要查询的字符长度
        int needLength = needle.length();
        int hayLength = haystack.length();
        char[] hayChars = haystack.toCharArray();
        for (int i = index; i < hayLength; i++) {
            if (hayChars[i] == needFirst) {
                // 剩余字符不足
                if (hayLength - i < needLength) {
                    return -1;
                } else {
                    String subHay = haystack.substring(i);
                    if (subHay.startsWith(needle)) {
                        return i;
                    } else {
                        return getIndex(needle, haystack, ++i);
                    }
                }
            }
        }
        return -1;
    }

}
